<!DOCTYPE html>
<html lang="zh-CN">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>2021年2月7日leetcode刷题笔记 | 月藤的博客</title>
    <meta name="generator" content="VuePress 1.8.0">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/katex.min.css">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/github-markdown-css/2.10.0/github-markdown.min.css">
    <meta name="description" content="简单的介绍">
    
    <link rel="preload" href="/assets/css/0.styles.a2e941e0.css" as="style"><link rel="preload" href="/assets/js/app.c7d9ff18.js" as="script"><link rel="preload" href="/assets/js/2.cd56dec9.js" as="script"><link rel="preload" href="/assets/js/46.e28c1031.js" as="script"><link rel="prefetch" href="/assets/js/10.21f484f8.js"><link rel="prefetch" href="/assets/js/11.5e166696.js"><link rel="prefetch" href="/assets/js/12.c56c19a2.js"><link rel="prefetch" href="/assets/js/13.3e31b609.js"><link rel="prefetch" href="/assets/js/14.3db3e5e6.js"><link rel="prefetch" href="/assets/js/15.cc75d7c3.js"><link rel="prefetch" href="/assets/js/16.5546d343.js"><link rel="prefetch" href="/assets/js/17.69b8a0f2.js"><link rel="prefetch" href="/assets/js/18.271396c8.js"><link rel="prefetch" href="/assets/js/19.bd4b0386.js"><link rel="prefetch" href="/assets/js/20.4a48d936.js"><link rel="prefetch" href="/assets/js/21.23862f34.js"><link rel="prefetch" href="/assets/js/22.95b3bd0a.js"><link rel="prefetch" href="/assets/js/23.d7c85d8e.js"><link rel="prefetch" href="/assets/js/24.c6d6dd3c.js"><link rel="prefetch" href="/assets/js/25.bb664de8.js"><link rel="prefetch" href="/assets/js/26.619789c7.js"><link rel="prefetch" href="/assets/js/27.54beb19d.js"><link rel="prefetch" href="/assets/js/28.8d77923a.js"><link rel="prefetch" href="/assets/js/29.7a771891.js"><link rel="prefetch" href="/assets/js/3.a0dd59cc.js"><link rel="prefetch" href="/assets/js/30.73e03cd7.js"><link rel="prefetch" href="/assets/js/31.a9a1ae37.js"><link rel="prefetch" href="/assets/js/32.66082a76.js"><link rel="prefetch" href="/assets/js/33.73a91496.js"><link rel="prefetch" href="/assets/js/34.da867ae2.js"><link rel="prefetch" href="/assets/js/35.6fac5ae2.js"><link rel="prefetch" href="/assets/js/36.0d6f5d22.js"><link rel="prefetch" href="/assets/js/37.c16a4955.js"><link rel="prefetch" href="/assets/js/38.3391e103.js"><link rel="prefetch" href="/assets/js/39.2e00541f.js"><link rel="prefetch" href="/assets/js/4.7f4b5eea.js"><link rel="prefetch" href="/assets/js/40.22b54e67.js"><link rel="prefetch" href="/assets/js/41.ea3ea4f8.js"><link rel="prefetch" href="/assets/js/42.3ae1db24.js"><link rel="prefetch" href="/assets/js/43.ecd8c202.js"><link rel="prefetch" href="/assets/js/44.f7609015.js"><link rel="prefetch" href="/assets/js/45.0db6f0b1.js"><link rel="prefetch" href="/assets/js/47.32d7164d.js"><link rel="prefetch" href="/assets/js/48.3aeaffda.js"><link rel="prefetch" href="/assets/js/49.33dab1c0.js"><link rel="prefetch" href="/assets/js/5.80c2b38b.js"><link rel="prefetch" href="/assets/js/50.6e41bca8.js"><link rel="prefetch" href="/assets/js/51.37e89a7c.js"><link rel="prefetch" href="/assets/js/52.e60e1d45.js"><link rel="prefetch" href="/assets/js/53.7a9c00ba.js"><link rel="prefetch" href="/assets/js/54.a214a30e.js"><link rel="prefetch" href="/assets/js/6.133fd621.js"><link rel="prefetch" href="/assets/js/7.79403511.js"><link rel="prefetch" href="/assets/js/8.04726c3a.js"><link rel="prefetch" href="/assets/js/9.a86daf82.js">
    <link rel="stylesheet" href="/assets/css/0.styles.a2e941e0.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">月藤的博客</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="https://ziphold.gitee.io/blog/#/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  旧博客（停止更新）
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><a href="https://rattonlzh.github.io/homepage/homepage.html" target="_blank" rel="noopener noreferrer" class="nav-link external">
  常用网址导航（停止更新）
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="Select language" class="dropdown-title"><span class="title">Languages</span> <span class="arrow down"></span></button> <button type="button" aria-label="Select language" class="mobile-dropdown-title"><span class="title">Languages</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/草稿/2021年2月7日leetcode刷题笔记.html" class="nav-link">
  zh-CN
</a></li><li class="dropdown-item"><!----> <a href="/en/" class="nav-link">
  en-US
</a></li></ul></div></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><div class="avatar"><img src="/assets/img/avatar.2b77755b.png" alt srcset></div> <div style="z-index: 999"><iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width="298" height="52" src="//music.163.com/outchain/player?type=2&id=28283137&auto=1&height=32"></iframe></div> <nav class="nav-links"><div class="nav-item"><a href="https://ziphold.gitee.io/blog/#/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  旧博客（停止更新）
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><a href="https://rattonlzh.github.io/homepage/homepage.html" target="_blank" rel="noopener noreferrer" class="nav-link external">
  常用网址导航（停止更新）
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="Select language" class="dropdown-title"><span class="title">Languages</span> <span class="arrow down"></span></button> <button type="button" aria-label="Select language" class="mobile-dropdown-title"><span class="title">Languages</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/草稿/2021年2月7日leetcode刷题笔记.html" class="nav-link">
  zh-CN
</a></li><li class="dropdown-item"><!----> <a href="/en/" class="nav-link">
  en-US
</a></li></ul></div></div> <!----></nav>  <ul class="sidebar-links"><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading open"><span>随便说说</span> <span class="arrow down"></span></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/%E9%9A%8F%E4%BE%BF%E8%AF%B4%E8%AF%B4/" class="sidebar-link">首页</a></li><li><a href="/随便说说/学习新编程语言的关注点.html" class="sidebar-link">学习新编程语言的关注点</a></li></ul></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>知识点总结</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>考研专区</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>读书笔记</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>开发资料</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>配置记录</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>思维导图</span> <span class="arrow right"></span></p> <!----></section></li><li><a href="/friend_link.html" class="sidebar-link">友情链接</a></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="_2021年2月7日leetcode刷题笔记"><a href="#_2021年2月7日leetcode刷题笔记" class="header-anchor">#</a> 2021年2月7日leetcode刷题笔记</h1> <p>重复子字符串的判断</p> <p>找出重复子串的性质，如下：</p> <ul><li>重复子串必然是原字符串的前缀</li> <li>重复子串长度必然整除原字符串的长度</li> <li>重复子串的长度必然小于等于原字符串的一半</li></ul> <p>因此，问题可以转化为枚举所有前缀，判断某个前缀是否为原字符串的重复子串，则问题性质如下：</p> <ul><li>设前缀长度为T， 则 存在 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>c</mi><mi>h</mi><mi>a</mi><mi>r</mi><mo>[</mo><mi>i</mi><mo>−</mo><mi>T</mi><mo>]</mo><mo>=</mo><mi>c</mi><mi>h</mi><mi>a</mi><mi>r</mi><mo>[</mo><mi>i</mi><mo>]</mo><mo separator="true">,</mo><mi>i</mi><mo>∈</mo><mo>[</mo><mi>T</mi><mo separator="true">,</mo><mi>n</mi><mo>−</mo><mn>1</mn><mo>]</mo></mrow><annotation encoding="application/x-tex">char[i - T] = char [i], i \in [T, n - 1]</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit">c</span><span class="mord mathit">h</span><span class="mord mathit">a</span><span class="mord mathit" style="margin-right:0.02778em;">r</span><span class="mopen">[</span><span class="mord mathit">i</span><span class="mbin">−</span><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="mclose">]</span><span class="mrel">=</span><span class="mord mathit">c</span><span class="mord mathit">h</span><span class="mord mathit">a</span><span class="mord mathit" style="margin-right:0.02778em;">r</span><span class="mopen">[</span><span class="mord mathit">i</span><span class="mclose">]</span><span class="mpunct">,</span><span class="mord mathit">i</span><span class="mrel">∈</span><span class="mopen">[</span><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="mpunct">,</span><span class="mord mathit">n</span><span class="mbin">−</span><span class="mord mathrm">1</span><span class="mclose">]</span></span></span></span>,</li></ul> <p>根据这个性质则可以判断重复子串，理论时间复杂度是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><msup><mi>n</mi><mn>2</mn></msup><mo>)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.8141079999999999em;"></span><span class="strut bottom" style="height:1.064108em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord"><span class="mord mathit">n</span><span class="vlist"><span style="top:-0.363em;margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">)</span></span></span></span>， 事实上除了检验真正重复子串的那趟循环需要遍历几乎整个字符串，其余情况可能只检查几个字符就已经判别出不可能是重复子串，直接跳过，最终性能比后面使用kmp算法（时间复杂度为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">O( n )</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathit">n</span><span class="mclose">)</span></span></span></span> ）的性能还要好</p> <div class="language-c++ extra-class"><pre class="language-text"><code>class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        for (int i = 1; i &lt;= n / 2; i++) {
            if (n % i == 0) {
                bool match = true;
                for (int j = i; j &lt; n; j++) {
                    if (s[j] != s[j - i]) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return true;
                }
            }
        }
        return false;

    }
};
</code></pre></div><p>方法二：使用kmp算法</p> <p>经过数学证明，只要s+s除去第一个字符和最后一个字符得到的字符串包含子串s，就可以确定s是重复子字符串， 问题转化为字符串匹配问题，使用kmp算法 ，复杂度为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">O (n)</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathit">n</span><span class="mclose">)</span></span></span></span></p> <div class="language-go extra-class"><pre class="language-go"><code><span class="token keyword">func</span> <span class="token function">repeatedSubstringPattern</span><span class="token punctuation">(</span>s <span class="token builtin">string</span><span class="token punctuation">)</span> <span class="token builtin">bool</span> <span class="token punctuation">{</span>
    n <span class="token operator">:=</span> <span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span>
    next <span class="token operator">:=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> n<span class="token punctuation">)</span>
    next<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span>
    i <span class="token operator">:=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token comment">// i是当前最长匹配前缀的最后一个元素的下标</span>
    j <span class="token operator">:=</span> <span class="token number">0</span><span class="token comment">// 第j+1个字符失配时更新next[j]</span>
    <span class="token keyword">for</span> j <span class="token operator">&lt;</span> n <span class="token operator">-</span><span class="token number">1</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> i <span class="token operator">==</span> <span class="token operator">-</span><span class="token number">1</span> <span class="token operator">||</span> s<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> s<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token punctuation">{</span>
            j<span class="token operator">++</span>
            i<span class="token operator">++</span>
            <span class="token keyword">if</span> s<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> s<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token punctuation">{</span>
                next<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> next<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
            <span class="token punctuation">}</span><span class="token keyword">else</span> <span class="token punctuation">{</span>
                next<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> i
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span><span class="token keyword">else</span> <span class="token punctuation">{</span>
            i <span class="token operator">=</span> next<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    t <span class="token operator">:=</span> s <span class="token operator">+</span> s
    i <span class="token operator">=</span> <span class="token number">0</span>
    j <span class="token operator">=</span> <span class="token number">1</span>
    tn <span class="token operator">:=</span> n <span class="token operator">*</span> <span class="token number">2</span>
    <span class="token keyword">for</span> i <span class="token operator">&lt;</span> n <span class="token operator">&amp;&amp;</span> j <span class="token operator">&lt;</span> tn <span class="token punctuation">{</span>
        <span class="token keyword">if</span> i <span class="token operator">==</span> <span class="token operator">-</span><span class="token number">1</span> <span class="token operator">||</span> s<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> t<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token punctuation">{</span>
            i<span class="token operator">++</span>
            j<span class="token operator">++</span>
        <span class="token punctuation">}</span><span class="token keyword">else</span> <span class="token punctuation">{</span>
            i <span class="token operator">=</span> next<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> i <span class="token operator">==</span> n <span class="token operator">&amp;&amp;</span> j <span class="token operator">&lt;</span> tn<span class="token punctuation">;</span> 
<span class="token punctuation">}</span>
</code></pre></div><ol start="1332"><li><p>删除回文子序列</p> <p>一开始我想的是找最长的回文子序列，然后删除，继续判断，但我不会找最长的回文子序列，而且即使找到感觉也很复杂</p> <p>回顾题意， 字符串只含有两种字母</p> <p>直接法：删除所有a， 再删除所有b，2次；如果本身是回文字符串，那就只删除1次</p></li></ol></div> <footer class="page-edit"><!----> <!----> <a rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh"><img alt="知识共享许可协议" src="" style="border-width:0"></a><br>本作品采用<a rel="license" href="http://creativecommons.org/licenses/by/4.0/">知识共享署名 4.0 国际许可协议</a>进行许可。

   
</footer> <!---->  <footer style="text-align:center;">备案号： 粤ICP备2021020303号</footer></main></div><div class="global-ui"><!----></div></div>
    <script src="/assets/js/app.c7d9ff18.js" defer></script><script src="/assets/js/2.cd56dec9.js" defer></script><script src="/assets/js/46.e28c1031.js" defer></script>
  </body>
</html>
